package com.cat.dynamicPlanning;

/**
 *   @description https://leetcode.cn/problems/regular-expression-matching/
 *   @author 曲大人的喵
 *   @create 2025/9/2 20:28
 *   @since JDK17
 */

public class Solution56 {
    boolean f(char[] s1, char[] s2, int i, int j) {
        if (i == s1.length) {
            if (j == s2.length) {
                return true;
            } else {
                return (j + 1 < s2.length && s2[j + 1] == '*') && f(s1, s2, i, j + 2);
            }
        } else if (j == s2.length) {
            return false;
        } else { // i 没有到终点
            if (j + 1 == s2.length || s2[j + 1] != '*') {
                return (s1[i] == s2[j] || s2[j] == '.') && f(s1, s2, i + 1, j + 1);
            } else {
                boolean p1 = f(s1, s2, i, j + 2); // 0个直接跳过去
                boolean p2 = (s1[i] == s2[j] || s2[j] == '.') && f(s1, s2, i + 1, j);
                return p1 || p2;
            }
        }
    }

    public boolean isMatch(String s, String p) {
        return f(s.toCharArray(), p.toCharArray(), 0, 0);
    }
}
